Sagemath|基于大整数分解的Rabin加密

问题概述

分析

使用sagemeth进行破解运算&＃xff0c;运算过程大约15秒。

首先将N质因数分解成两个素数p&＃xff0c;q&＃xff1a;
p&＃61;990932843298892349238943242791&＃xff0c;
q&＃61;2387883598789374983927498237627。

再用模幂计算出&＃xff1a;


可得&＃xff1a;
m_p&＃61;358546986862207226911256688941&＃xff0c;
m_q&＃61;1790411145826943505290886300376&＃xff1b;

欧几里得辗转相除法求出满足sp &＃43; tq&＃61;1的s、t的值&＃xff1a;

s&＃61;417850213941792666727100662729&＃xff1b;
t&＃61;-173401040479659357453257331194。

再用中国剩余定理解得x1&＃xff0c;x2&＃xff0c;x3&＃xff0c;x4&＃xff1a;

X1&＃61;1180750646513203924856355379026414770979645149607&＃xff1b;
X2&＃61;2366232284013966098921140426254459982575397735186553227547350
X3&＃61;874422063025296895941599983057263334241694752879172800315388
X4&＃61;1491810220989849953626053647122053003712729397078360072381569。

猜想将其转换成16进制看一下是否有进一步的含义&＃xff0c;x1&＃xff0c;x2&＃xff0c;x3&＃xff0c;x4转换后的结果如图&＃xff1a;

进一步4个一组&＃xff0c;查询编码&＃xff0c;看看是否有对应的意义&＃xff0c;x1所对应的汉字如下&＃xff0c;x2、x3、x4无对应含义&＃xff1a;